import java.util.ArrayList;
import java.util.List;

/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution89 {

    public static void main(String args[]){
        Solution89 s = new Solution89();
        System.out.println(s.grayCode(3));
    }

    List<Integer> ret = new ArrayList<>();
    int[] mp;
    public List<Integer> grayCode(int n) {
        mp = new int[1 << n];
        dfs(0, n);
        return ret;
    }

    public void dfs(int v, int n){
        ret.add(v);
        mp[v] = 1;
        for(int i = 0 ; i < n ; i ++){
            int nv = v ^ (1 << i);
            if(mp[nv] == 0){
                dfs(nv, n);
                break;
            }
        }
    }
}
